package likou;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @title: LRUCache
 * @author: zp
 * @date: 2021/9/12 17:26
 */
class LRUCache {
    int capacity;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer> doubleLinkedList;
    //保存数据的容器
    class Node<K,V>{
        Node<K,V> prev;
        Node<K,V> next;
        K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            prev=next=null;
        }

        public Node() {
            prev=next=null;
        }


    }

    class DoubleLinkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;
        //构造方法
        public DoubleLinkedList(){
            head=new Node<>();
            tail=new Node<>();
            head.next=tail;
            tail.prev=head;
        }
        //把元素添加到头
        public void addHead(Node<K,V> node){
            node.next=head.next;
            node.prev=head;
            head.next.prev=node;
            head.next=node;

        }

        //删除节点
        public void removeNode(Node<K,V> node){
            node.next.prev=node.prev;
            node.prev.next=node.next;
            node.next=null;
            node.prev=null;
        }

        //返回最后一个节点
        public Node getLastNode(){
            return tail.prev;
        }

    }
    public LRUCache(int capacity) {
        map = new HashMap<>();
        doubleLinkedList=new DoubleLinkedList<>();
        this.capacity=capacity;

    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node<Integer,Integer> node=map.get(key);
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node<Integer,Integer> node = map.get(key);
            node.value=value;
            map.put(key,node);
            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }else{
            if(map.size()==capacity){
                Node<Integer,Integer> lastNode=doubleLinkedList.getLastNode();
                map.remove(lastNode.key);
                doubleLinkedList.removeNode(lastNode);
            }
        }
        Node<Integer,Integer> node=new Node<>(key,value);
        map.put(key,node);
        doubleLinkedList.addHead(node);
    }

}
